from tkinter.font import names

red = 0
black = 1
class RedBlackNode:
    def __init__(self,value):
        self.value = value
        self.left = None
        self.right = None
        self.p = None
        self.color = red
class RedBlackTree:
    def __init__(self):
        self.root = None
    def left_rotate(self,x:RedBlackNode):
        y = x.right
        x_parent = x.p
        if x_parent is None:#x is root
            self.root = y
        elif x_parent.left == x:#x is left child
            x_parent.left = y
        elif x_parent.right == x:#x is right child
            x_parent.right = y
        y.p = x_parent
        if y.left:#y has left child
            y.left.p = x
        x.right = y.left
        y.left = x
        x.p = y
    def right_rotate(self,x:RedBlackNode):
        y = x.left
        x_parent = x.p
        if x_parent is None:#x is root
            self.root = y
        elif x_parent.left == x:#x is left child
            x_parent.left = y
        elif x_parent.right == x:#x is right child
            x_parent.right = y
        y.p = x_parent
        if y.right:#y has right child
            y.right.p = x
        x.left = y.right
        y.right = x
        x.p = y
    def insert(self,value):
        node = RedBlackNode(value)
        if not self.root:
            self.root = node
            node.color = black
        else:
            x = self.root
            while x:
                y = x
                if node.value < x.value:
                    x = x.left
                else:
                    x = x.right
            if node.value < y.value:
                y.left = node
            else:
                y.right = node
            node.p = y
        self.insert_fixup(node)
    def insert_fixup(self,node:RedBlackNode):
        parent = node.p
        while parent and parent.color == red:
            gparent = parent.p
            if gparent.left == parent:
                uncle = gparent.right
                if uncle and uncle.color == red:
                    gparent.color = red
                    uncle.color = black
                    parent.color = black
                    node = gparent
                    parent = node.p
                    continue
                if parent.right == node:
                    self.left_rotate(parent)
                    parent,node = node,parent
                self.right_rotate(gparent)
                gparent.color = red
                parent.color = black

            else:
                uncle = gparent.left
                if uncle and uncle.color == red:
                    gparent.color = red
                    uncle.color = black
                    parent.color = black
                    node = gparent
                    parent = node.p
                    continue
                if parent.left == node:
                    self.right_rotate(parent)
                    parent,node = node,parent
                self.left_rotate(gparent)
                gparent.color = red
                parent.color = black
        self.root.color = black
    def mid_order_traversal(self,node:RedBlackNode):
        if node:
            self.mid_order_traversal(node.left)
            print(node.value)
            self.mid_order_traversal(node.right)
    def rbtree_print(self,node:RedBlackNode,key,direction):
        if node:
            if direction == 0:
                #用f-string方式打印
                print(f"根节点 is {node.value}")
            else:
                print(f"{node.value}是{key}的{"right" if direction == 1 else "left"}子节点 "
                      f",是{"红" if node.color == 0 else "黑"}色的")
            self.rbtree_print(node.left,node.value,-1)
            self.rbtree_print(node.right,node.value,1)

if __name__ == '__main__':
    number_list = (7,4,1,8,5,2,9,6,3)
    tree = RedBlackTree()
    for number in number_list:
        tree.insert(number)

    tree.rbtree_print(tree.root,0,0)
